import java.util.ArrayList;

/**
 * 排序算法
 * @author Daowei Guan
 */
public class Sort {
    //直接插入排序
    public static void DirectInsert(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int cur = arr[i];//记录当前要插入的数
            int index = i-1;//记录需要插入到的位置 初值为有序表表尾index

            //将满足插入条件的数插入到正确的位置
            while(index >= 0 && cur < arr[index] ){
                arr[index + 1] = arr[index];
                index--;
            }
            //排除cur已经有序的情况
            if(index + 1 != i){
                //插入到有序表中
                arr[index + 1] = cur;
            }
        }
    }


    //折半插入排序
    public static void BinInsert(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int cur = arr[i];//记录当前要插入的数
            int low = 0,high = i -1;//折半查找区间
            while(low <= high){
                int mid = (low + high) / 2;
                if(cur < arr[mid]){
                    high = mid -1;
                }else{
                    low = mid + 1;
                }
            }
            //找到插入位置后 记录后移
            for (int j = i - 1; j >= high + 1 ; --j) {
                arr[j+1] = arr[j];
            }
            //插入
            arr[high + 1] = cur;
        }
    }



    //一次步长为step的希尔排序
    private static void shellSortOnce(int[] arr,int step){
        for (int i = step; i < arr.length; i+=step) {
            int cur = arr[i];//记录当前要插入的数
            int index = i-step;//记录需要插入到的位置 初值为分组后有序表表尾index

            //将满足插入条件的数插入到正确的位置
            while(index >= 0 && cur < arr[index] ){
                arr[index + step] = arr[index];
                index-=step;
            }
            //排除cur已经有序的情况
            if(index + step != i){
                //插入到有序表中
                arr[index + step] = cur;
            }
        }
    }

    //希尔排序
    public static void shellSort(int[] arr){
        for (int i = arr.length/2; i > 0; i/=2) {
            //根据一次递减的步长执行每次排序
            shellSortOnce(arr,i);
        }
    }


    //冒泡排序
    public static void bubbleSort(int[] arr){
        boolean flag = false;//flag 标记是否发生交换
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int t = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = t;
                    flag = true;//发生交换
                }
            }
            if (!flag)
                break;
            else
                flag = false;//重置flag,进行下次判断
        }
    }


    //对arr进行一趟快排(划分) 并返回排完后的枢轴位置
    private static int quickSortOnce(int[] arr,int low,int high){
        //用首元素作为枢轴数值
        int pivotKey = arr[low];
        while(low<high){
            //寻找最右侧小于枢轴的值 然后移动到最左侧
            while(high > low && arr[high] >= pivotKey)  --high;
            arr[low] = arr[high];
            //寻找最左侧大于枢轴的值 然后移动到最右侧
            while(low < high &&arr[low] <= pivotKey)  ++low;
            arr[high] = arr[low];
        }
        //将枢轴放入
        arr[low] = pivotKey;
        return low;
    }

    private static void quickSort(int[] arr,int low,int high){
        if(low < high){//递归结束条件
            int pivot = quickSortOnce(arr, low, high);
            quickSort(arr,low,pivot-1);
            quickSort(arr,pivot+1,high);
        }
    }
    //快排
    public static void qSort(int[] arr){
        quickSort(arr,0,arr.length-1);
    }

    //简单选择排序
    public static void selectSort(int[] arr){
        for (int i = 0; i < arr.length - 1; i++) {
            int min = arr[i];//假设当前值最小
            int minIndex = i;//记录最小值的索引
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < min) {
                    min = arr[j];
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }
    }


    //堆排序
    public static void heapSort(int[] arr) {
        //将无序序列构建成一个堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        //将堆顶元素和末尾元素交换,将最大元素放置数组末端
        //重新调整至堆结构,然后继续将堆顶元素和当前末尾元素交换,以此往复
        for (int i = arr.length - 1; i > 0; i--) {
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, i);
        }
    }

    /**
     * 将二叉树调整为堆
     *
     * @param arr    待调整的数组
     * @param i      表示非叶子结点在数组中索引
     * @param length 表示对多少个元素继续调整,length逐渐减少
     */
    private static void adjustHeap(int[] arr, int i, int length) {
        int temp = arr[i];
        //k=2i+1是i的左子节点
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
            if (k + 1 < length && arr[k] < arr[k + 1])//左子节点的值<右子节点的值
                k++;//指向右节点
            if (arr[k] > temp) {//如果子结点的值>父节点的值
                arr[i] = arr[k];//将较大的值赋给当前节点
                i = k;//i指向k,继续循环比较
            } else
                break;
        }
        //for循环后,已经将以i为父结点的树的最大值,放在了顶部
        arr[i] = temp;//将temp值放到调整后的位置
    }


    //归并排序
    public static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;//中间索引
            mergeSort(arr, left, mid, temp);//向左递归分解
            mergeSort(arr, mid + 1, right, temp);//向右递归分解
            merge(arr, left, mid, right, temp);//合并
        }
    }

    //合并方法
    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;//i为指向左边序列第一个元素的索引
        int j = mid + 1;//j为指向右边序列第一个元素的索引
        int t = 0;//指向临时temp数组的当前索引

        //先把左右两边有序数据按规则存入temp数组中,直到有一边的数据全部填充temp中
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[t] = arr[i];
                t++;
                i++;
            } else {
                temp[t] = arr[j];
                t++;
                j++;
            }
        }

        //将有剩余数据的一边全部存入temp中
        while (i <= mid) {//左边序列有剩余元素
            temp[t] = arr[i];
            t++;
            i++;
        }
        while (j <= right) {//右边序列有剩余元素
            temp[t] = arr[j];
            t++;
            j++;
        }

        /**
         * 将temp中的元素拷贝到arr中
         *  注意:不是每次都拷贝全部元素
         *  第一次:tempLeft=0,right=1
         *  第二次:tempLeft=2,right=3
         *  第三次:tempLeft=0,right=3
         */
        t = 0;
        int tempLeft = left;
        while (tempLeft <= right) {
            arr[tempLeft] = temp[t];
            t++;
            tempLeft++;
        }
    }


    //基数排序
    public static void radixSort(int[] arr) {
        //定义一个二维数组,表示10个桶,每一个桶就是一个一维数组
        int[][] bucket = new int[10][arr.length];//可能每个桶不会用满,所以基数排序是使用空间换时间的经典算法
        //定义一个一维数组记录每个桶每次放入数据的个数
        int[] bucketCounts = new int[10];
        //找到数组中最大数
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max)
                max = arr[i];
        }
        //获得最大数的位数，即为循环的次数,也就是要判断的总位数(个、十、百、千)
        int maxLength = (max + "").length();

        //针对每个元素的位进行比较
        for (int c = 0, n = 1; c < maxLength; c++, n *= 10) {
            for (int i = 0; i < arr.length; i++) {
                //取出每个元素对应位的值(个位-->十位-->百位---)
                int digit = arr[i] / n % 10;//个位:%10  十位:/10再%10  百位:/100再%10
                //放入桶中
                bucket[digit][bucketCounts[digit]] = arr[i];
                bucketCounts[digit]++;
            }
            int index = 0;
            //遍历每个桶,将桶中的数据放回到原数组
            for (int j = 0; j < 10; j++) {
                if (bucketCounts[j] != 0) {//如果桶不为空
                    for (int k = 0; k < bucketCounts[j]; k++) {
                        arr[index] = bucket[j][k];
                        index++;
                    }
                }
                bucketCounts[j] = 0;//清空每个桶的数据
            }
        }
    }


}
